home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / basic / qsort.bas < prev    next >
BASIC Source File  |  1984-04-14  |  3KB  |  72 lines
  1. 10 ''       QUICKSORT SORTING ALGORITHM DEMONSTRATION
  2. 20 ''               NELSON FORD  APRIL 1984
  3. 30 ''
  4. 40 DEFINT A-Z:  CLS:  KEY OFF:  COLOR 7,0:  LAST=26:  DIM DTA$(LAST)
  5. 50 FOR I=1 TO LAST:  READ DTA$(I):  NEXT
  6. 60 DATA H,G,C,V,B,N,M,A,S,D,F,Z,X,J,K,L,Q,I,O,W,E,R,T,Y,U,P
  7. 70 FLAG1=-1: FLAG2=-1: FLAG3=-1
  8. 75 COLR1= 7:  COLR2= 15:  COLR3= 0
  9. 80 GOSUB 460
  10. 90 '
  11. 100 '''''''''''sort:
  12. 110 '
  13. 120 BOT(1)=1:  TOP(1)=LAST:  PLY=1
  14. 130   WHILE PLY > 0
  15. 140 IF BOT(PLY) >= TOP(PLY) THEN PLY=PLY-1: GOTO 300
  16. 150 I=BOT(PLY)-1:  J=TOP(PLY):  KY$=DTA$(J)
  17. 160      WHILE I < J
  18. 170 I=I+1:  J=J-1
  19. 180 LN=180:  WHILE DTA$(I) < KY$:  I=I+1: GOSUB 330:  WEND
  20. 190 IF FLAG1 THEN GOSUB 530
  21. 200 LN=200:  WHILE DTA$(J) > KY$ AND J > I:  J=J-1:  GOSUB 330: WEND
  22. 210 IF FLAG2 THEN GOSUB 600
  23. 220 IF I<J THEN LN=220:  GOSUB 690  'go swap
  24. 230     WEND
  25. 240 IF FLAG3 THEN GOSUB 630
  26. 250 J=TOP(PLY):  IF I=J THEN 280
  27. 260 LN=260: GOSUB 330
  28. 270 IF DTA$(I) > DTA$(J) THEN LN=270:  GOSUB 690
  29. 280 IF I-BOT(PLY) < TOP(PLY)-I                                                         THEN  BOT(PLY+1)=BOT(PLY):  TOP(PLY+1)=I-1:  BOT(PLY)=I+1:                      ELSE  TOP(PLY+1)=TOP(PLY):  BOT(PLY+1)=I+1:  TOP(PLY)=I-1
  30. 290 PLY=PLY+1
  31. 300   WEND
  32. 310 COLOR 15: PRINT "SORTED:   ";: FOR I=1 TO 26: PRINT " "DTA$(I);: NEXT
  33. 320 END
  34. 330 '
  35. 340 PRINT LN"  ";
  36. 350   FOR X=FIRST TO LAST
  37. 360 FG=7: BG=0   'foreground and background colors
  38. 370 IF X = I THEN FG=15
  39. 380 IF X = J THEN BG= 7:  IF FG=7 THEN FG=0
  40. 390 IF X = TOP(PLY) THEN FG=FG+16
  41. 400 IF X < BOT(PLY) OR X > TOP(PLY) THEN FG=1
  42. 410 COLOR FG,BG
  43. 420 PRINT " " DTA$(X);:  COLOR 7,0
  44. 430   NEXT: PRINT
  45. 440 RETURN
  46. 450 '
  47. 460 PRINT "FIRST SEARCH UP THE LIST UNTIL AN ";: COLOR 15
  48. 470 PRINT "ITEM ";: COLOR 7
  49. 480 PRINT "LARGER THAN THE ";: COLOR 23
  50. 490 PRINT "KEY";: COLOR 7: PRINT " IS FOUND,": PRINT
  51. 500 PRINT "PROGRAM  ": PRINT "LINE #":  XXX=9
  52. 510 RETURN
  53. 520 '
  54. 530 PRINT :PRINT "THEN SEARCH DOWN THE LIST UNTIL AN ";: COLOR 0,7
  55. 540 PRINT " ITEM";: COLOR 7,0
  56. 550 PRINT " LESS THAN THE ";: COLOR 23
  57. 560 PRINT "KEY";: COLOR 7: PRINT " IS FOUND.  (GO";
  58. 570 INPUT X$:  FLAG1=0
  59. 580 RETURN
  60. 590 '
  61. 600 INPUT "IF POINTERS HAVE NOT CROSSED, SWAP ITEMS AND CONTINUE.  (GO"; X$
  62. 610 FLAG2=0: RETURN
  63. 620 '
  64. 630 PRINT"WHEN THE POINTERS CROSS, DIVIDE THE LIST AND SORT THE SMALLER PART."
  65. 640 PRINT"BUT FIRST, COMPARE THE ";: COLOR 15
  66. 650 PRINT"ITEM";: COLOR 7: PRINT " AT THE BREAK TO THE ";: COLOR 23:
  67. 660 PRINT "KEY":  COLOR 7: PRINT "      AND SWAP IF ";: COLOR 15
  68. 670 PRINT"ITEM";: COLOR 7: INPUT " IS LARGER.  (GO"; X$
  69. 680 FLAG3=0:  RETURN
  70. 690 SWAP DTA$(I), DTA$(J): PRINT TAB(27)"SWAP " DTA$(J)   " AND " DTA$(I)
  71. 700 GOSUB 330: RETURN
  72.